Project Sekai - ✅-crypto-eeveelutions

Eeveelutions - 500 points

Category: Crypto Description: My flag keeps evolving... Author: aparker Files:

Tags: No tags.

Sutx pinned a message to this channel. 04/28/2023 7:59 PM

@fleming wants to collaborate

@unpickled admin bot wants to collaborate

@layka_ wants to collaborate

interesting one

21:56

from Crypto.Util.number import getPrime, inverse, bytes_to_long
from math import gcd
import re
import string
import random

while True:
    p = getPrime(1024)
    q = getPrime(1024)

    n = p * q
    e = 3
    phi = (p-1)*(q-1)

    if gcd(phi, e) == 1:
        d = inverse(e, phi)
        break

with open('flag.txt', 'r') as f:
    flag = f.read().strip()

pad1 = ''.join(random.choices(string.ascii_uppercase + string.ascii_lowercase + string.digits, k=12))
pad2 = ''.join(random.choices(string.ascii_uppercase + string.ascii_lowercase + string.digits, k=12))

evolutions = ['umbreon', 'sylveon', 'jolteon', 'flareon', 'glaceon', 'leafeon']
e1 = random.choice(evolutions)
while True:
    e2 = random.choice(evolutions)
    if e2 != e1:
        break

flag1 = re.sub("eevee", e1, flag) + pad1
flag2 = re.sub("eevee", e2, flag) + pad2

f1 = bytes_to_long(flag1.encode())
f2 = bytes_to_long(flag2.encode())

ct1 = pow(f1, e, n)
ct2 = pow(f2, e, n)

print(f"n = {n}")
print(f"e = {e}")
print(f"ct1 = {ct1}")
print(f"ct2 = {ct2}")

21:56

sending source in case anyone on phone

21:57

(e1, e2) is gonna be bruted ig

21:59

ok interesting

this is franklin reiter

so we need to recover f1 and f2?

(r11 + x)^3 + r12

im not sure if the ct1 and ct2 have any relations

layka_

(r11 + x)^3 + r12

sorry whats this

22:00

didnt know about it

that re.sub is replacing some string in the flag

yeah

if we reformulate it into polynomial

coppersmith attack for related-messages i would have not remembered that, nice one layka (edited)

layka_

(r11 + x)^3 + r12

not simole as that

22:02

but can be written as polynomial

22:02

with gcd as the solution

22:02

but first ig we need to recover some coeffs

wait to recover coeffs

22:03

wouldnt we need to know e1,e2?

22:03

ig we can brute em but

the messages are related but we need to recover coeefs

ye

so basically the polys are in the form (x1 + 2^len(x1) . e1 + 2^len(x1+e1) . x2).2^(12*7*8) + pad1 (edited)

ti recover pad1 and pad2 short pad attack can't work right ?

layka_

so basically the polys are in the form (x1 + 2^len(x1) . e1 + 2^len(x1+e1) . x2).2^(12*7*8) + pad1 (edited)

update on that: pad1 + 2^(12*8).(x1 + 2^len(x1).(e1 + 2^(7*8 )x2)) (edited)

22:27

eevee = IV so it will be at first of the flag or at the end

@Violin wants to collaborate

23:09

@kanon wants to collaborate

@Utaha wants to collaborate

test.sage

3.73 KB

08:55

one-hour solve script

08:57

main idea is to enumerate e1, e2, and the position where it's being substituted, so that we know the estimated different between flag1 and flag2

08:58

and essentially, you have equation of the form: (x + error) ^ 3 = ct1 (x + diff) ^ 3 = ct2 where the diff is th estimated different, and error is the difference introduced by random padding, which is upper bounded by 2^96

08:59

and by a painful Euclidean algorithm (line 22-37), we can eliminate x in the above two equations (edited)

09:00

given that diff is a constant (by enumeration), we get a polynomial of error with degree 10

09:00

and we can use coppersmith method to find it because error is indeed small (edited)

09:05

diff = 2412054218119662037878742186860195397130437926481023823094617398472162924240590642533924204345574088235433328640 error = 5003658853324167671940717347

Utaha

used /ctf solve

✅ Challenge solved.

veeery good well done